11448 - Who said crisis/11448.2.cpp

   1 #include <stdio.h>
   2 #include <math.h>
   3 #include <iostream>
   4
   5 using namespace std;
   6
   7 #define MAXDIGITS       10001           /* maximum length bignum */
   8
   9 #define PLUS            1               /* positive sign bit */
  10 #define MINUS           -1              /* negative sign bit */
  11
  12 typedef struct {
  13         char digits[MAXDIGITS];         /* represent the number */
  14         int signbit;                    /* 1 if positive, -1 if negative */
  15         int lastdigit;                  /* index of high-order digit */
  16 } bignum;
  17
  18
  19 void subtract_bignum(bignum *a, bignum *b, bignum *c);
  20 void zero_justify(bignum *n);
  21 int compare_bignum(bignum *a, bignum *b);
  22
  23 void print_bignum(bignum *n)
  24 {
  25         int i;
  26
  27         if (n->signbit == MINUS) printf("-");
  28         for (i=n->lastdigit; i>=0; i--)
  29                 printf("%c",'0'+ n->digits[i]);
  30
  31         printf("\n");
  32 }
  33
  34 void int_to_bignum(int s, bignum *n)
  35 {
  36         int i;                          /* counter */
  37         int t;                          /* int to work with */
  38
  39         if (s >= 0) n->signbit = PLUS;
  40         else n->signbit = MINUS;
  41
  42         for (i=0; i<MAXDIGITS; i++) n->digits[i] = (char) 0;
  43
  44         n->lastdigit = -1;
  45
  46         t = abs(s);
  47
  48         while (t > 0) {
  49                 n->lastdigit ++;
  50                 n->digits[ n->lastdigit ] = (t % 10);
  51                 t = t / 10;
  52         }
  53
  54         if (s == 0) n->lastdigit = 0;
  55 }
  56
  57 void string_to_bignum(const string &s, bignum *n)
  58 {
  59         int i;                          /* counter */
  60
  61         if (s.size() == 0){
  62           int_to_bignum(0, n);
  63           return;
  64         }
  65
  66         if (s[0] != '-') n->signbit = PLUS;
  67         else n->signbit = MINUS;
  68
  69         for (i=0; i<MAXDIGITS; i++) n->digits[i] = (char) 0;
  70
  71         n->lastdigit = -1;
  72
  73         int len = s.size();
  74         for (i=0; i<len; ++i){
  75           n->lastdigit++;
  76           n->digits[n->lastdigit] = s[i] - '0';
  77         }
  78 }
  79
  80
  81 void initialize_bignum(bignum *n)
  82 {
  83         int_to_bignum(0,n);
  84 }
  85
  86
  87 int max(int a, int b)
  88 {
  89         if (a > b) return(a); else return(b);
  90 }
  91
  92 /*      c = a +-/* b;   */
  93
  94 void add_bignum(bignum *a, bignum *b, bignum *c)
  95 {
  96         int carry;                      /* carry digit */
  97         int i;                          /* counter */
  98
  99         initialize_bignum(c);
 100
 101         if (a->signbit == b->signbit) c->signbit = a->signbit;
 102         else {
 103                 if (a->signbit == MINUS) {
 104                         a->signbit = PLUS;
 105                         subtract_bignum(b,a,c);
 106                         a->signbit = MINUS;
 107                 } else {
 108                         b->signbit = PLUS;
 109                         subtract_bignum(a,b,c);
 110                         b->signbit = MINUS;
 111                 }
 112                 return;
 113         }
 114
 115         c->lastdigit = max(a->lastdigit,b->lastdigit)+1;
 116         carry = 0;
 117
 118         for (i=0; i<=(c->lastdigit); i++) {
 119                 c->digits[i] = (char) (carry+a->digits[i]+b->digits[i]) % 10;
 120                 carry = (carry + a->digits[i] + b->digits[i]) / 10;
 121         }
 122
 123         zero_justify(c);
 124 }
 125
 126
 127 void subtract_bignum(bignum *a, bignum *b, bignum *c)
 128 {
 129         int borrow;                     /* has anything been borrowed? */
 130         int v;                          /* placeholder digit */
 131         int i;                          /* counter */
 132
 133         initialize_bignum(c);
 134
 135         if ((a->signbit == MINUS) || (b->signbit == MINUS)) {
 136                 b->signbit = -1 * b->signbit;
 137                 add_bignum(a,b,c);
 138                 b->signbit = -1 * b->signbit;
 139                 return;
 140         }
 141
 142         if (compare_bignum(a,b) == PLUS) {
 143                 subtract_bignum(b,a,c);
 144                 c->signbit = MINUS;
 145                 return;
 146         }
 147
 148         c->lastdigit = max(a->lastdigit,b->lastdigit);
 149         borrow = 0;
 150
 151         for (i=0; i<=(c->lastdigit); i++) {
 152                 v = (a->digits[i] - borrow - b->digits[i]);
 153                 if (a->digits[i] > 0)
 154                         borrow = 0;
 155                 if (v < 0) {
 156                         v = v + 10;
 157                         borrow = 1;
 158                 }
 159
 160                 c->digits[i] = (char) v % 10;
 161         }
 162
 163         zero_justify(c);
 164 }
 165
 166 int compare_bignum(bignum *a, bignum *b)
 167 {
 168         int i;                          /* counter */
 169
 170         if ((a->signbit == MINUS) && (b->signbit == PLUS)) return(PLUS);
 171         if ((a->signbit == PLUS) && (b->signbit == MINUS)) return(MINUS);
 172
 173         if (b->lastdigit > a->lastdigit) return (PLUS * a->signbit);
 174         if (a->lastdigit > b->lastdigit) return (MINUS * a->signbit);
 175
 176         for (i = a->lastdigit; i>=0; i--) {
 177                 if (a->digits[i] > b->digits[i]) return(MINUS * a->signbit);
 178                 if (b->digits[i] > a->digits[i]) return(PLUS * a->signbit);
 179         }
 180
 181         return(0);
 182 }
 183
 184 void zero_justify(bignum *n)
 185 {
 186         while ((n->lastdigit > 0) && (n->digits[ n->lastdigit ] == 0))
 187                 n->lastdigit --;
 188
 189         if ((n->lastdigit == 0) && (n->digits[0] == 0))
 190                 n->signbit = PLUS;      /* hack to avoid -0 */
 191 }
 192
 193
 194 void digit_shift(bignum *n, int d)              /* multiply n by 10^d */
 195 {
 196         int i;                          /* counter */
 197
 198         if ((n->lastdigit == 0) && (n->digits[0] == 0)) return;
 199
 200         for (i=n->lastdigit; i>=0; i--)
 201                 n->digits[i+d] = n->digits[i];
 202
 203         for (i=0; i<d; i++) n->digits[i] = 0;
 204
 205         n->lastdigit = n->lastdigit + d;
 206 }
 207
 208
 209
 210 void multiply_bignum(bignum *a, bignum *b, bignum *c)
 211 {
 212         bignum row;                     /* represent shifted row */
 213         bignum tmp;                     /* placeholder bignum */
 214         int i,j;                        /* counters */
 215
 216         initialize_bignum(c);
 217
 218         row = *a;
 219
 220         for (i=0; i<=b->lastdigit; i++) {
 221                 for (j=1; j<=b->digits[i]; j++) {
 222                         add_bignum(c,&row,&tmp);
 223                         *c = tmp;
 224                 }
 225                 digit_shift(&row,1);
 226         }
 227
 228         c->signbit = a->signbit * b->signbit;
 229
 230         zero_justify(c);
 231 }
 232
 233
 234 void divide_bignum(bignum *a, bignum *b, bignum *c)
 235 {
 236         bignum row;                     /* represent shifted row */
 237         bignum tmp;                     /* placeholder bignum */
 238         int asign, bsign;               /* temporary signs */
 239         int i,j;                        /* counters */
 240
 241         initialize_bignum(c);
 242
 243         c->signbit = a->signbit * b->signbit;
 244
 245         asign = a->signbit;
 246         bsign = b->signbit;
 247
 248         a->signbit = PLUS;
 249         b->signbit = PLUS;
 250
 251         initialize_bignum(&row);
 252         initialize_bignum(&tmp);
 253
 254         c->lastdigit = a->lastdigit;
 255
 256         for (i=a->lastdigit; i>=0; i--) {
 257                 digit_shift(&row,1);
 258                 row.digits[0] = a->digits[i];
 259                 c->digits[i] = 0;
 260                 while (compare_bignum(&row,b) != PLUS) {
 261                         c->digits[i] ++;
 262                         subtract_bignum(&row,b,&tmp);
 263                         row = tmp;
 264                 }
 265         }
 266
 267         zero_justify(c);
 268
 269         a->signbit = asign;
 270         b->signbit = bsign;
 271 }
 272
 273
 274
 275 main()
 276 {
 277   string a, b;
 278   int n;
 279   cin >> n;
 280   while (n--){
 281     cin >> a >> b;
 282     reverse(a.begin(), a.end());
 283     reverse(b.begin(), b.end());
 284     bignum n1,n2,n3;
 285     string_to_bignum(a, &n1);
 286     string_to_bignum(b, &n2);
 287     subtract_bignum(&n1, &n2, &n3);
 288     print_bignum(&n3);
 289   }
 290   return 0;
 291
 292 }